public class Main {
    /**
     * 添加逗号
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            long N = in.nextLong();
//            String s = N + "";
//            char[] ss = s.toCharArray();
//            StringBuffer sb = new StringBuffer();
//            int count = 0;//统计数字个数
//            for (int i = ss.length - 1; i >= 0; i--) {
//                count++;
//                if (count > 3) {
//                    sb.append(",");
//                    sb.append(ss[i]);
//                    count = 1;
//                } else {
//                    sb.append(ss[i]);
//                }
//            }
//            System.out.println(sb.reverse().toString());
//        }
//    }
//


/**
 * 青蛙跳台阶
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int[] dp= new int[n + 1];//小细节: 要注意多一个位置 因为最后一个台阶也要跳
//            dp[0] = 1;
//            dp[1] = 1;
//            for(int i = 2; i <= n; i++) {
//                dp[i] = dp[i - 1] + dp[i - 2];
//            }
//            System.out.println(dp[n]);
//        }
//    }

/**
 * 最长回文子串
 */
//    public class Solution {
//        public int getLongestPalindrome (String A) {
//            int n = A.length();
//            //中心扩展算法
//            char[] s = A.toCharArray();
//            int ret = 0;
//            for (int i = 0; i < n; i++) {
//                //以i位置为中心然后向两边扩展
//                int left = i - 1;
//                int right = i + 1;
//                //回文串是奇数长度情况
//                while (left >= 0 && right < n) {
//                    if (s[left] == s[right]) {
//                        left--;
//                        right++;
//                    } else {
//                        break;
//                    }
//                }
//                ret = Math.max(ret, right - left - 1);
//                //偶数情况
//                left = i;
//                right = i + 1;
//                while (left >= 0 && right < n) {
//                    if (s[left] == s[right]) {
//                        left--;
//                        right++;
//                    } else {
//                        break;
//                    }
//                }
//                ret = Math.max(ret, right - left - 1);
//            }
//            return ret;
//        }
//    }

    /**
     * 牛牛冲砖五
     *
      */
//    public class Main{
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int T = in.nextInt();
//            while(T-- > 0) {
//                int n = in.nextInt();
//                int k = in.nextInt();
//                char[] s = in.next().toCharArray();
//                int ret = 0;
//                int count = 0;//统计连胜次数
//                for(char c : s) {
//                    if(c == 'W') {
//                        count++;
//                        ret = ret + (count >= 3 ? k : 1);
//                    } else {
//                        ret--;
//                        count = 0;
//                    }
//                }
//                System.out.println(ret);
//            }
//        }
//    }

    /**\
     * 过河卒
      */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int m = in.nextInt();
//            int x = in.nextInt();
//            int y = in.nextInt();
//
//            long[][] dp = new long[n + 2][m + 2];
//            //初始化
//            dp[0][1] = 1;
//            //注意修改x y 的位置
//            x += 1;
//            y += 1;
//            //填表
//            for (int i = 1; i < n + 2; i++) {
     //一定是满足了条件才能使用公式
//                for (int j = 1; j < m + 2; j++) {
//                    if ( (i == x && j == y) || (i != x && j != y &&
//                            Math.abs(i - x) + Math.abs(j - y) == 3) ) {
//                        //该位置被马占据或者马可以拦截
//                        dp[i][j] = 0;
//                    } else {
//                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//                    }
//                }
//            }
//            System.out.println(dp[n + 1][m + 1]);
//        }
//    }


    /**
     * 分割等和子集
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            while (in.hasNextInt()) {
//                int n = in.nextInt();
//                int[] arr = new int[n];
//                int capacity = 0;
//                for (int i = 0; i < n; i++) {
//                    arr[i] = in.nextInt();
//                    capacity += arr[i];
//                }
//                if (capacity % 2 != 0) {
//                    System.out.println(false);
//                    continue;
//                }
//                boolean[][] dp = new boolean[n + 1][capacity / 2 + 1];
//                dp[0][0] = true;
//                dp[1][0] = true;
//                for (int i = 1; i <= n; i++) {
//                    for (int j = 1; j <= capacity / 2; j++) {
//                        dp[i][j] = dp[i - 1][j] || (j - arr[i - 1] >= 0 ? dp[i - 1][j - arr[i - 1]] : false);
//                    }
//                }
//                System.out.println(dp[n][capacity / 2]);
//            }
//        }
//    }


/**
 * 主持人调度1
 */
//    public class Solution {
//        public boolean hostschedule (ArrayList<ArrayList<Integer>> schedule) {
//            //先按照左端点排序区间---必须声明比较器
//            schedule.sort((a, b) -> {
//                return a.get(0).compareTo(b.get(0));
//            });
//            for(int i = 1; i < schedule.size(); i++) {
//                int left = schedule.get(i).get(0);//当位置的左端点
//                int right = schedule.get(i - 1).get(schedule.get(i - 1).size() - 1);//前一个区间的右端点
//                if(left >= right) {
//                    continue;
//                } else {
//                    return false;
//                }
//            }
//            return true;
//        }
//    }

    /**
     * 笨小猴
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            //先统计每个字母出现的次数
//            int[] tmp = new int[27];
//            char[] word = in.next().toCharArray();
//            int maxn = 0;
//            int minn = 0x3f3f3f3f;
//            for (char c : word) {
//                tmp[c - 'a'] += 1;
//
//            }
//            for (int x : tmp) {
//                if (x > maxn) {
//                    maxn = x;
//                }
//
//                if (x != 0 && minn > x) {
//                    minn = x;
//                }
//            }
//            //然后判断是否是质数
//            if (isPrime(maxn - minn)) {
//                System.out.println("Lucky Word");
//                System.out.println(maxn - minn);
//            } else {
//                System.out.println("No Answer");
//                System.out.println(0);
//            }
//        }
//
//        //判断一个数是否是质数
//        public static boolean isPrime(int n) {
//            if (n < 1) return false; //1 以下的数不是质数
//            if (n == 1) return false;
//            if (n == 2) return true; //2是唯一的偶质数
//            //试除法逻辑
//            for (int i = 2; i * i <= n; i++) {
//                if (n % i == 0) {
//                    return false;
//                }
//            }
//            return true;
//        }
//
//    }


    /**
     * 买卖股票最佳时机2
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextInt()) { // 注意 while 处理多个 case
//                int n = in.nextInt();
//                if (n == 0) {
//                    System.out.println(0);
//                    continue;
//                }
//                int[] arr = new int[n];
//                for (int i = 0; i < n; i++) {
//                    arr[i] = in.nextInt();
//                }
//                //贪心 将所有上升区间都+上
//                int ret = 0;
//                for (int i = 1; i < n; i++) {
//                    if(arr[i] > arr[i - 1]) {
//                        ret += arr[i] - arr[i - 1];//加上区间增量
//                    }
//                }
//                System.out.println(ret);
//            }
//        }
//    }

/**
 * 游游水果大礼包
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            long n = in.nextInt();
//            long m = in.nextInt();
//            long a = in.nextInt();
//            long b = in.nextInt();
//            long ret = 0;
//            //枚举一号礼包出现的次数
//            for(long x = 0; x <= Math.min(n / 2, m); x++) {
//                long y = Math.min((m - x) / 2, n - 2 * x);//二号礼包的数量
//                ret = Math.max(ret, x * a + y * b);
//            }
//            System.out.println(ret);
//        }
//    }


    /**
     * 倒置字符串
      */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            while (in.hasNextLine()) {
//                String str = in.nextLine();
//                //先把每个单词抽取出来
//                String[] word = str.split(" ");
//                //然后将个单词拼接起来
//                StringBuilder ret = new StringBuilder();
//                for (int i = word.length - 1; i >= 0; i--) {
//                    ret.append(word[i]);
//                    if(i != 0) {
//                        ret.append(" ");
//                    }
//                }
//                System.out.println(ret.toString());
//            }
//        }
//    }

}
